
var MedianFinder = function () {
  this.maxHeap = []
  this.minHeap = []
};
MedianFinder.prototype.siftDown = function (arr, inx, compare) {
  compare = compare ? compare : (a, b) => a > b
  while (true) {
      let tempInx = inx
      if (2 * inx + 1 < arr.length && compare(arr[2 * inx + 1], arr[inx])) {
          tempInx = 2 * inx + 1
      }
      if (2 * inx + 2 < arr.length && compare(arr[2 * inx + 2], arr[tempInx])) {
          tempInx = 2 * inx + 2
      }
      if (tempInx === inx) break
      let temp = arr[inx]
      arr[inx] = arr[tempInx]
      arr[tempInx] = temp
      inx = tempInx
  }
}
MedianFinder.prototype.siftUp = function (arr, inx, compare) { 
  compare = compare ? compare : (a, b) => a > b
  while (inx > 0) {
      let parentInx = Math.ceil(inx / 2) - 1
      if (compare(arr[inx], arr[parentInx])) {
          let temp = arr[inx]
          arr[inx] = arr[parentInx]
          arr[parentInx] = temp
          inx = parentInx
      } else {
        break
      }
  }
}
/** 
* @param {number} num
* @return {void}
*/
MedianFinder.prototype.addNum = function (num) {
  
  if (this.minHeap.length === 0) {
      this.minHeap.push(num)
  } else {
      if (this.minHeap.length === this.maxHeap.length) { // 小堆和大堆数据持平
          if (num >= this.maxHeap[0]) {
              this.minHeap.push(num)
              this.siftUp(this.minHeap, this.minHeap.length - 1, (a, b) => a < b)
          } else {
              let max = this.maxHeap[0]
              this.maxHeap[0] = num
              this.siftDown(this.maxHeap, 0)
              this.mindHeap.push(max)
          }
      } else { // 小堆数量比大堆多一个
          if (num <= this.minHeap[0]) {
              this.maxHeap.push(num)
              this.siftUp(this.maxHeap, this.maxHeap.length - 1)
          } else {
              let min = this.minHeap[0]
              this.minHeap[0] = num
              this.siftDown(this.minHeap, 0, (a, b) => a < b)
              this.maxHeap.push(min)
          }
      }
  }
};

/**
* @return {number}
*/
MedianFinder.prototype.findMedian = function () {
  if (this.minHeap.length === 0) return null
  console.log(this.minHeap);
  
  if (this.minHeap.length > this.maxHeap.length) return this.minHeap[0]
  return (this.minHeap[0] + this.maxHeap[0]) / 2
};

/**
* Your MedianFinder object will be instantiated and called as such:
* var obj = new MedianFinder()
* obj.addNum(num)
* var param_2 = obj.findMedian()
*/
// let medianFinder = new MedianFinder();
// medianFinder.addNum(1);    // arr = [1]
// medianFinder.addNum(2);    // arr = [1, 2]
// medianFinder.findMedian(); // 返回 1.5 ((1 + 2) / 2)
// medianFinder.addNum(3);    // arr[1, 2, 3]
// console.log(medianFinder.findMedian());
